package com.it.zhangjun.arithmetic.递归;

/**
 * 斐波那契数列：1、1、2、3、5、8、13、21、34、……
 *
 * @author jun.zhang6
 * @date 2020/10/24
 */
public class Fib {
    public static void main(String[] args) {
        System.out.println(fib6(5));
    }

    public static int fib6(int n) {
        if (n <= 2) {
            return 1;
        }
        int first = 1;
        int second = 1;
        for (int i = 3; i <= n; i++) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

    /**
     * 位运算代替模运算
     *
     * @param n
     * @return
     */
    public static int fib5(int n) {
        if (n <= 2) {
            return 1;
        }
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];
        }
        return array[n & 1];
    }

    /**
     * 滚动数组
     *
     * @param n
     * @return
     */
    public static int fib4(int n) {
        if (n <= 2) {
            return 1;
        }
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2];
        }
        return array[n % 2];
    }

    /**
     * 去除递归
     *
     * @param n
     * @return
     */
    public static int fib3(int n) {
        if (n <= 2) {
            return 1;
        }
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        for (int i = 3; i <= n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array[n];
    }

    /**
     * 递归解法
     *
     * @param n
     * @return
     */
    public static int fib1(int n) {
        if (n <= 2) {
            return 1;
        }
        return fib2(n - 1) + fib2(n - 2);
    }

    /**
     * 记忆化
     *
     * @param n
     * @return
     */
    public static int fib2(int n) {
        if (n <= 2) {
            return 1;
        }
        int[] array = new int[n + 1];
        return fib2(array, n);
    }

    public static int fib2(int[] array, int n) {
        if (array[n] != 0) {
            return array[n];
        }
        return fib2(n - 1) + fib2(n - 2);
    }


}
